/*
 * @lc app=leetcode.cn id=1438 lang=javascript
 *
 * [1438] 绝对差不超过限制的最长连续子数组
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} limit
 * @return {number}
 */

/**
 * 遍历nums，分别设置窗口长度为 length 为 1 -> nums.length
 * 随着length增大，判断length中最大值减最小值是否满足条件
 * 1 0 模型 
 * 
 * 二分法设置length 
 * 单调队列记录窗口最大最小值
 * 
 */
function check(nums, length, limit){
  const maxQ = [];
  const minQ = [];

  for (let i = 0; i < nums.length; i++) {
    while(minQ.length && nums[i] < nums[minQ[minQ.length - 1]]) minQ.pop();
    while(maxQ.length && nums[i] > nums[maxQ[maxQ.length - 1]]) maxQ.pop();
    minQ.push(i);
    maxQ.push(i);

    if(i + 1 < length) continue;

    if(i - maxQ[0] == length) maxQ.shift();
    if(i - minQ[0] == length) minQ.shift();

    if(nums[maxQ[0]] - nums[minQ[0]] <= limit) return true;
  }
  return false;
}

function search(l, r, nums, limit){
  if(l == r ) return l;
  // length取值范围 1 -> nums.length
  // 二分查找设置length

  const length = l + (( r - l + 1 ) >> 1); 

  // 检测是否有满足条件的长度为length的窗口
  if(check(nums, length, limit)){
    l = length;
  } else {
    r = length - 1;
  }
  return search(l, r, nums, limit);
}

var longestSubarray = function(nums, limit) {
  return search(1, nums.length, nums, limit);
}
// @lc code=end

